"""
二叉树的各种遍历算法
"""
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 使用队列实现二叉树的层次遍历
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        queue = []
        if not root:
            return result
        queue.append(root)
        while len(queue) > 0:
            root = queue.pop(0)
            result.append(root.val)
            if root.left:
                queue.append(root.left)
            if root.right:
                queue.append(root.right)
        return result

    # 非递归--堆栈实现先序遍历
    # 在栈不为空时循环：先将根节点入栈，出栈p并访问它，若其右孩子节点不为空则将右节点入栈，若其左孩子节点不为空则将其入栈
    def PreOrder(self, root: TreeNode) -> List:
        result = []
        stack = []
        if not root:
            return result
        stack.append(root)
        while len(stack) > 0:
            root = stack.pop()
            result.append(root.val)
            if root.right:
                stack.append(root.right)
            if root.left:
                stack.append(root.left)
        return result

    # 递归--前序遍历
    def PreOrder_Recursion(self, root: TreeNode) -> List:
        result = []

        def dfs(root):
            if not root:
                return
            result.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return result

    # 非递归--堆栈实现中序遍历
    def InOrder(self, root: TreeNode) -> List:
        result = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                temp = stack.pop()
                result.append(temp.val)
                root = temp.right
        return result

    # 递归--中序遍历
    def InOrder_Recursion(self, root: TreeNode) -> List:
        result = []

        def dfs(root):
            if not root:
                return
            dfs(root.left)
            result.append(root.val)
            dfs(root.right)
        dfs(root)
        return result

    # 非递归--堆栈实现后序遍历
    def PostOrder(self, root: TreeNode) -> List:
        result = []
        stack = []
        while root or stack:
            while root:
                result.append(root.val)
                stack.append(root)
                root = root.right
            if stack:
                top = stack.pop()
                root = top.left
        return result[::-1]

    # 递归--后序遍历
    def PostOrder_Recursion(self, root: TreeNode) -> List:
        result = []

        def dfs(root):
            if not root:
                return
            dfs(root.left)
            dfs(root.right)
            result.append(root.val)

        dfs(root)
        return result


# 按层输出，和层次遍历有所区别
class Other:
    def func1(self, root: TreeNode) -> List[List[int]]:
        result = []
        queue = []
        if not root:
            return result
        queue.append(root)
        while len(queue) > 0:
            result.append([node.val for node in queue])
            temp = []
            for node in queue:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
            queue = temp
        return result


if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.left.left = TreeNode(10)
    root.left.right = TreeNode(18)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)

    x = Solution()
    y = Other()
    print(y.func1(root))
